//给定一个二叉树，确定它是否是一个完全二叉树。 
//
// 百度百科中对完全二叉树的定义如下： 
//
// 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：
//第 h 层可能包含 1~ 2h 个节点。） 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：[1,2,3,4,5,6]
//输出：true
//解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。
// 
//
// 示例 2： 
//
// 
//
// 输入：[1,2,3,4,5,null,7]
//输出：false
//解释：值为 7 的结点没有尽可能靠向左侧。
// 
//
// 
//
// 提示： 
//
// 
// 树中将会有 1 到 100 个结点。 
// 
// Related Topics 树 
// 👍 130 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * Java：二叉树的完全性检验
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P958_CheckCompletenessOfABinaryTree {
    public static void main(String[] args) {
        Solution solution = new P958_CheckCompletenessOfABinaryTree().new Solution();
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7, 8, 9);
        MyUtil.print(solution.isCompleteTree(treeNode));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isCompleteTree(TreeNode root) {
            return process(root).isCBT;
        }

        public Info process(TreeNode node) {
            if (node == null) {
                return new Info(true, true, 0);
            }

            Info li = process(node.left);
            Info ri = process(node.right);
            int height = Math.max(li.height, ri.height) + 1;
            int h = li.height - ri.height;
            boolean isFBT = li.isFBT && ri.isFBT && (h == 0);
            boolean isCBT = false;
            // 左满，右满，高度差 = 0|1
            if (li.isFBT && ri.isFBT && (h == 0 || h == 1)) {
                isCBT = true;
            }
            // 左完全，右满，高度差 = 1
            if (li.isCBT && ri.isFBT && (h == 1)) {
                isCBT = true;
            }
            // 左满，右完全，高度差 = 0
            if (li.isFBT && ri.isCBT && (h == 0)) {
                isCBT = true;
            }
            return new Info(isCBT, isFBT, height);
        }

        class Info {
            boolean isCBT; // 是否完全二叉树
            boolean isFBT; // 是否满二叉树
            int height;

            public Info(boolean isCBT, boolean isFBT, int height) {
                this.isCBT = isCBT;
                this.isFBT = isFBT;
                this.height = height;
            }
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

}